package club.yunqiang.arithmetic.sort;

import java.util.Arrays;

/**
 * 插入排序
 * 
 * @author YunQiang
 *
 */
public class InsertionSort {

	/**
	 * 私有化构造方法
	 */
	private InsertionSort() {

	}

	@SuppressWarnings({ "rawtypes", "unchecked" })
	public static void sort(Comparable[] comparables) {
		for (int i = 1; i < comparables.length; i++) {
			// 寻找comparables[i]最合适的插入位置

//			// 写法1
//			for (int j = i; j > 0; j--)
//				if (arr[j].compareTo(arr[j - 1]) < 0)
//					swap(arr, j, j - 1);
//				else
//					break;

//			// 写法2
//			for (int j = i; j > 0 && arr[j].compareTo(arr[j - 1]) < 0; j--)
//				swap(arr, j, j - 1);

			// 写法3
			Comparable element = comparables[i];
			// j保存element应该插入的位置
			int j = i;
			for (; (j > 0) && (element.compareTo(comparables[j - 1]) < 0); j--) {
				comparables[j] = comparables[j - 1];
			}
			comparables[j] = element;
		}
	}

	public static void main(String[] args) {
		Integer[] integers = SortTestHelper.generateNearlyOrderedArray(6000, 20);
		Integer[] copy = Arrays.copyOf(integers, integers.length);

		SortTestHelper.testSort(InsertionSort.class.getName(), integers);
		SortTestHelper.testSort(SelectionSort.class.getName(), copy);

		System.exit(0);
	}

}
